import java.util.Stack;

public class BinaryTreeTest {
    //孩子表示法实现二叉树
    static class TreeNode {
        //1.建立数据域、左孩子的引用和右孩子的引用
        public char val;
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //开始创建二叉树
    public TreeNode createTree() {
        //2.创建二叉树的结点
        TreeNode treeNodeA = new TreeNode('A');
        TreeNode treeNodeB = new TreeNode('B');
        TreeNode treeNodeC = new TreeNode('C');
        TreeNode treeNodeD = new TreeNode('D');
        TreeNode treeNodeE = new TreeNode('E');
        TreeNode treeNodeF = new TreeNode('F');
        TreeNode treeNodeG = new TreeNode('G');
        TreeNode treeNodeH = new TreeNode('H');

        //3.有左孩子赋值到左边，有右孩子的赋值到右边并确定根节点
        treeNodeA.left = treeNodeB;
        treeNodeB.left = treeNodeD;
        treeNodeB.right = treeNodeE;
        treeNodeE.right = treeNodeH;
        treeNodeA.right = treeNodeC;
        treeNodeC.left = treeNodeF;
        treeNodeC.right = treeNodeG;
        return treeNodeA;//确定根节点
    }

    //二叉树面试题
    /*
     * NO.1 检查两棵树是否相同
     * */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //pheq其中有个等于null就说明不相同
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        //p和q相同
        if (p == null && q == null) {
            return true;
        }
        //结点的值不相同
        if (p.val != q.val) {
            return false;
        }
        //调用方法继续找p和q的下一个左树和下一个右树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /*
     * NO.2 另一棵树的子树
     * */
    public boolean isSubTree(TreeNode root, TreeNode subRoot) {
        //如果root和subRoot为空 - subRoot不是root的子树
        if (root == null || subRoot == null) {
            return false;
        }
        //调用方法判断两棵树是不是相同的
        if (isSameTree(root, subRoot)) {
            return true;//相同说明subRoot是root的子树
        }
        //subRoot是root.left的子树
        if (isSubTree(root.left, subRoot)) {
            return true;
        }
        //subRoot是root.right的子树
        if (isSubTree(root.right, subRoot)) {
            return true;
        }
        //全部遍历未找到返回false
        return false;
    }

    /*
     * NO.3 对称二叉树
     * */
    public boolean isSymmetric(TreeNode root) {
        //如果root为空则是对称的
        if (root == null) {
            return true;
        }
        //判断root的左树和右树
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        //左树和右树一个等于空一个不等于空
        if (leftTree == null && rightTree != null || leftTree != null && rightTree == null) {
            return false;
        }
        //左树和右树等于空
        if (leftTree == null && rightTree == null ) {
            return true;
        }
        //左树的值不等于右树的值
        if (leftTree.val != rightTree.val) {
            //不对称
            return false;
        }
        //走到这说明左和右要么都为空要么都不为空并且左右的值不一样
        //调用方法查找左树和右树
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }

    /*
     * NO.4 翻转二叉树
     * */
    public TreeNode invertTree(TreeNode root) {
        //root为空
        if (root == null) {
            return null;
        }
        //定义一个临时变量 - 交换结点的值
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        //调用方法去翻转左树和右树
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /*
     * NO.5 平衡二叉树
     * */
    public boolean isBalanced(TreeNode root) {
        //为空
        if (root == null) {
            return true;//为空是平衡的情况
        }
        //不为空的情况
        int leftH = maxdepth(root.left);//求左树的高度
        int rightH = maxdepth(root.right);//求右树的高度
        //左树减右树的绝对值小于2并且调用方法找左边和右边是不是平衡的
        return Math.abs(leftH - rightH) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }

    //求二叉树的高度
    public int maxdepth(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        int leftHeight = maxdepth(root.left);//找左边
        int rightHeight = maxdepth(root.right);//找右边
        //返回左和右的最大高度加1
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    /*
     * NO.6 二叉书的构建及遍历
     * */
    public static int i = 0;
    public static TreeNode createNode(String str) {
        TreeNode root = null;
        //当前的字符不等于#
        if (str.charAt(i) != '#') {
            //新建一个结点
            root = new TreeNode(str.charAt(i));
            //找字符串的下一个字符
            i++;
            //调用方法找到左边和右边的位置
            root.left = createNode(str);
            root.right = createNode(str);
        }else {
            //如果是字符#则不创建结点
            i++;//找到下一个
        }
        return root;
    }

    /*
     * @ 思路1：将个结点到p和q路径上的所有结点压入到两个栈中
     * NO.7 给定一个二叉树，找到该树中两个结点的最近公共祖先
     * */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //定义两个栈来分别存放p和q的结点
        Stack<TreeNode> stackP = new Stack<>();
        //调用方法将p的结点压入到栈1中
        getPath(root, p, stackP);

        Stack<TreeNode> stackQ = new Stack<>();
        //调用方法将q的结点压入到栈2中
        getPath(root, q, stackQ);

        //求两个栈元素的个数
        int sizeP = stackP.size();//调用方法求个数
        int sizeQ = stackQ.size();

        //判断两个栈元素个数是相等的吗
        if (sizeP > sizeQ) {
            //两栈元素个数不等的情况且为p多
            int size = sizeP - sizeQ;//求差值
            //弹出这个差值元素
            while (size > 0) {
                stackP.pop();//弹出
                size--;
            }
        }else {
            //q多的情况
            int size = sizeQ - sizeP;//求差值
            //弹出这个差值元素
            while (size > 0) {
                stackQ.pop();//弹出
                size--;
            }
        }

        //此时两栈中元素个数一定相等 - 开始同时弹出同时比较
        while (stackP.peek() != stackQ.peek()) {
            //若不相等 - 弹出两栈不相等的元素
            stackP.pop();
            stackQ.pop();
        }
        //若相等即是公共祖先
        //此时栈顶就是两栈的公共祖先 - 返回即可
        //因为两栈此时的栈顶元素相等所以返回任意一个栈的栈顶即可
        return stackP.peek();//返回peek栈顶的元素但不弹出
    }

    //node是要找的位置
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        //二叉树和要找的位置是空的时候
        if (root == null || node == null) {
            return false;//不存在公共祖先
        }

        //如不是空的 - 将此时root的结点压入到栈中
        stack.push(root);
        //若找到了要找的位置
        if (root == node) {
            return true;
        }

        //调用方法判断左边是不是要找的位置
        boolean flag1 = getPath(root.left, node, stack);
        //返回true·表示找到了要找的位置
        if(flag1 == true) {
            return true;
        }

        //调用方法判断右边是不是要找的位置
        boolean flag2 = getPath(root.right, node, stack);
        //返回true·表示找到了要找的位置
        if(flag2 == true) {
            return true;
        }

        //压入的结点为空会走到这里 - 将它弹出
        stack.pop();
        //走到上面一个结点的位置
        return false;
    }

    /*
     * @ 思路2：二叉搜索树
     * NO.7 给定一个二叉树，找到该树中两个结点的最近公共祖先
     * */
    public TreeNode lowestCommonAncestors(TreeNode root, TreeNode p, TreeNode q) {
        //如果二叉树是空的
        if (root == null) {
            return null;//没有最近公共祖先
        }
        //若不是空的且p或者q等于root
        if(p == root || q == null) {
            //此时p或者q就是最近公共祖先
            return root;
        }
        //调用非法查找左右两边
        TreeNode leftTree = lowestCommonAncestors(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestors(root.right, p, q);
        //两边都不为空root是祖先
        if (leftTree != null && rightTree != null) {
            return root;
        } else if (leftTree != null) {
            //右边不是空
            return leftTree;
        } else if (rightTree != null) {
            //左边不是空
            return rightTree;
        } else {
            //左右都不是空
            return null;
        }
    }


    /*
     * NO.8 将一棵二叉搜索树排序成双向链表
     * */
    public class Test {
        TreeNode prev = null;

        public TreeNode Convert(TreeNode pRootOfTree) {
            if (pRootOfTree == null) {
                return null;
            }
            convertChild(pRootOfTree);
            //定义一个双向链表的头结点
            TreeNode head = pRootOfTree;//将此时接收的二叉树根节点赋值给head

            while (head.left != null) {
                //不等于空往左走
                head = head.left;
            }
            //循环结束 - head为空
            return head;//此时head就是双线链表的头结点
        }

        public void convertChild(TreeNode root) {

            //排成有序的双向链表
            if (root == null) {
                //为空返回
                return;
            }
            //调用方法找左边的结点
            convertChild(root.left);
            root.left = prev;//root左边改为空
            //prev为空无左右节点
            if (prev != null) {
                prev.right = root;
            }
            //若prev==null，prev会找到它的上一个节点
            prev = root;//prev找到下一个结点
            //调用方法找右边
            convertChild(root.right);//如果为空返回
        }
    }

    /*
     * NO.9 非递归实现二叉树的前序遍历
     * */
    public TreeNode  preorderTraversal(TreeNode root) {
        TreeNode cur = root;//定义cur代替root移动
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                //将cur压入到栈中
                stack.push(cur);
                System.out.print(cur.val + " ");//打印此时cur的值
                cur = cur.left;//cur往左走
            }
            //定义一个记录弹出栈顶元素的引用
            TreeNode top = stack.pop();
            cur = top.right;//cur等于当前弹出结点的右边
        }
        return root;
    }

    /*
     * NO.10 
     * */
}